home *** CD-ROM | disk | FTP | other *** search
- Path: keats.ugrad.cs.ubc.ca!not-for-mail
- From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
- Newsgroups: comp.lang.c
- Subject: Re: Special linked list
- Date: 7 Mar 1996 16:35:56 -0800
- Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
- Message-ID: <4hnvdcINN165@keats.ugrad.cs.ubc.ca>
- References: <4hn7ov$e1t@eng_ser1.erg.cuhk.hk>
- NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
-
- In article <4hn7ov$e1t@eng_ser1.erg.cuhk.hk>,
- ERiC LEE <cslee@cs.cuhk.hk> wrote:
- > Is there a method to build a linked list using struct & pointer,
- >where the linked list (in fact a two-dimensional linked list, where for
- >example, b3 has 2 pointers at b4 & a3, which is also pointed by b2 & c3)
- >is as shown below? (All the data are long integers)
-
- Yes there is. This loosely corresponds to a data structure known as a ``sparse
- matrix''.
-
- One way is to keep two arrays of pointers; a horizontal vector and a vertical
- vector. The horizontal vector contains chains that link elements horizontally.
- The vertical vector links---you guessed it---vertically. As in:
-
- x[0] x[1] x[2] x[3] ... x[n]
- | | | | |
- | v v | v
- y[0]----------->z(1,0)->z(2,0)----------------->z(n,0)-->
- | | | |
- v | | v v
- y[1]--->z(0,1)----------------->z(3,1)--------->z(n,1)-->
- . | | | | |
-
- . . . . . .
- . | | | | |
- y[m]----z(0,m)--------------------------------->z(n,m)-->
- | | | | |
- v v v v ... v
-
-
- The lists are typically doubly-linked. The idea is that using this data
- structure you can represent large matrices that are sparsely populated with
- elements without reserving storage for the whole matrix.
-
-
- --
-
-